package com.ldw.algorithm;


/**
 * 上楼梯问题扩展
 * 题目：一个楼梯有N阶，从下往上走，只有三种走法
 * 1.一步可以走一阶，
 * 2.一步走两阶
 * 3.一步可以走三阶
 * 有多少种走法？
 * 解:
 */
public class StepExtend {

    public static void main(String[] args) {

        System.out.println(step(5));

    }

    private static int step(int N) {
        int array[] = new int[N+1];

        if (N==0)
            return 0;

        array[0] = 0;
        if (N >= 1) array[1] =1;
        if (N >= 2) array[2] = 2;
        if (N >= 3) array[3] = 4;

        for (int i = 4; i <= N; i++) {
            array[i] = array[i - 1] + array[i - 2] + array[i - 3];
        }
        return array[N];

    }

}